class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> arr(m);
        for(int i = 0; i < m; ++i) // 存储最后一列查找在哪一行
        {
            arr[i] = matrix[i][n - 1];
        }

        auto pos = lower_bound(arr.begin(), arr.end(), target);
        if(pos == arr.end())
            return false;

        int i = pos - arr.begin(); // 在第i行
        vector<int> arr2(n);
        int k = 0;
        for(int j = 0; j < n; ++j)
        {
            arr2[k++] = matrix[i][j];
        }
        pos = lower_bound(arr2.begin(), arr2.end(), target);
        if(pos == arr.end() || *pos != target)
            return false;
        return true;
    }
};
/*
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> arr(m);
        for(int i = 0; i < m; ++i) // 存储最后一列查找在哪一行
        {
            arr[i] = matrix[i][n - 1];
        }
        auto pos = lower_bound(arr.begin(), arr.end(), target);
        if(pos == arr.end())
            return false;
        int i = pos - arr.begin(); // 在第i行
        return binary_search(matrix[i].begin(), matrix[i].end(), target);
    }
};*/